;(in-package 'user)

;;----------------------------------------------------------------------
;; Last Update  5-Oct-96 by EHN
;;
;; Language Technologies Institute
;; 11-712 -- Self-Paced Laboratory
;; Algorithms for NLP
;;
;; Module 1: Bottom-Up Chart Parser -- Test Code
;;
;; Copyright (c) 1996, Carnegie Mellon University, All Rights Reserved.

(defun generate-tests (infile outfile)

  "INFILE contains lists of symbols that are valid inputs to the chart
   parser; writes test inputs for RUN-TESTS to OUTFILE."

  (let (input (*print-parse-tree* nil)(*chart-trace* nil))
    (with-open-file (out outfile :direction :output :if-exists :supersede)
      (with-open-file (in infile :direction :input)
        (loop 
	 (setq input (read in nil in))
	 (when (eq input in)
	       (return))
	 (format out "~%")
	 (dolist (searchmode '(dfs bfs))
           (dolist (quitmode '(t nil))
             (let ((result (bottom-up-chart input searchmode quitmode)))
	       (format out "~%((:INPUT '~s '~s '~s)~% (:EXPECTED ~s))" 
		       input searchmode quitmode result)))))))))

(defun run-tests (function &optional (tests *chart-tests*))

  "FUNCTION should be a quoted function name, e.g.,
   'bottom-up-chart. See example *chart-tests* below for how the TESTS
    variable has to look."

  (let ((failures 0) input expected actual s)
    (format t "~%Testing function: ~s" function)
    (dolist (test tests (format t "~%~s tests failed." failures))
	    (setq input (rest (assoc :input test)))
	    (setq expected (second (assoc :expected test)))
	    (setq fncall (cons function input))
	    (setq actual (eval fncall))
	    (format t "~%~%Input: ~s~%Expected: ~s~%Actual: ~s"
		    input expected actual)
	    (setq actual (mapcar #'(lambda (s)
				     (list (entry-start s) 
					   (entry-end s) 
					   (entry-category s)
					   (or (entry-lexeme s)
					       (entry-children s)) 
					   (entry-id s)))
				 actual))
	    (cond ((equalp actual expected)
		   (format t "~%[Test Passed]"))
		  (t (incf failures)
		     (format t "~%[TEST FAILED!]"))))))

(defvar *chart-tests*)
(setq *chart-tests* '(

((:INPUT '(THE) 'DFS 'T)
 (:EXPECTED ((1 2 ART THE 1))))
((:INPUT '(THE) 'DFS 'NIL)
 (:EXPECTED ((1 2 ART THE 1))))
((:INPUT '(THE) 'BFS 'T)
 (:EXPECTED ((1 2 ART THE 1))))
((:INPUT '(THE) 'BFS 'NIL)
 (:EXPECTED ((1 2 ART THE 1))))

((:INPUT '(LARGE) 'DFS 'T)
 (:EXPECTED ((1 2 ADJ LARGE 1))))
((:INPUT '(LARGE) 'DFS 'NIL)
 (:EXPECTED ((1 2 ADJ LARGE 1))))
((:INPUT '(LARGE) 'BFS 'T)
 (:EXPECTED ((1 2 ADJ LARGE 1))))
((:INPUT '(LARGE) 'BFS 'NIL)
 (:EXPECTED ((1 2 ADJ LARGE 1))))

((:INPUT '(CAN) 'DFS 'T)
 (:EXPECTED ((1 2 N CAN 3))))
((:INPUT '(CAN) 'DFS 'NIL)
 (:EXPECTED ((1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN) 'BFS 'T)
 (:EXPECTED ((1 2 V CAN 1))))
((:INPUT '(CAN) 'BFS 'NIL)
 (:EXPECTED ((1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))

((:INPUT '(HOLDS) 'DFS 'T)
 (:EXPECTED ((1 2 V HOLDS 1))))
((:INPUT '(HOLDS) 'DFS 'NIL)
 (:EXPECTED ((1 2 V HOLDS 1))))
((:INPUT '(HOLDS) 'BFS 'T)
 (:EXPECTED ((1 2 V HOLDS 1))))
((:INPUT '(HOLDS) 'BFS 'NIL)
 (:EXPECTED ((1 2 V HOLDS 1))))

((:INPUT '(WATER) 'DFS 'T)
 (:EXPECTED ((1 2 N WATER 1))))
((:INPUT '(WATER) 'DFS 'NIL)
 (:EXPECTED ((1 2 NP (1) 2) (1 2 N WATER 1))))
((:INPUT '(WATER) 'BFS 'T)
 (:EXPECTED ((1 2 N WATER 1))))
((:INPUT '(WATER) 'BFS 'NIL)
 (:EXPECTED ((1 2 NP (1) 2) (1 2 N WATER 1))))

((:INPUT '(THE CAN) 'DFS 'T)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ART THE 1))))
((:INPUT '(THE CAN) 'DFS 'NIL)
 (:EXPECTED ((2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ART THE 1))))
((:INPUT '(THE CAN) 'BFS 'T)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ART THE 1))))
((:INPUT '(THE CAN) 'BFS 'NIL)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ART THE 1))))

((:INPUT '(LARGE CAN) 'DFS 'T)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN) 'DFS 'NIL)
 (:EXPECTED ((2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN) 'BFS 'T)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN) 'BFS 'NIL)
 (:EXPECTED ((1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))

((:INPUT '(THE LARGE CAN) 'DFS 'T)
 (:EXPECTED ((1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN) 'DFS 'NIL)
 (:EXPECTED ((3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN) 'BFS 'T)
 (:EXPECTED ((1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN) 'BFS 'NIL)
 (:EXPECTED ((1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

((:INPUT '(CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 4 S (4 8) 10) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((1 4 VP (2 8) 9) (1 4 S (4 8) 10) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 4 VP (2 8) 9) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))
((:INPUT '(CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 4 S (4 8) 10) (1 4 VP (2 8) 9) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))

((:INPUT '(CAN CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 5 S (4 14) 17) (2 5 VP (6 13) 14) (2 5 S (8 13) 15) (3 5 VP (10 12) 13) (4 5 NP (11) 12) (4 5 N WATER 11) (3 4 V HOLDS 10) (2 3 V CAN 5) (2 3 AUX CAN 6) (1 3 VP (1 8) 9) (2 3 NP (7) 8) (2 3 N CAN 7) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((1 5 VP (2 14) 16) (1 5 S (4 14) 17) (2 5 VP (6 13) 14) (2 5 S (8 13) 15) (3 5 VP (10 12) 13) (4 5 NP (11) 12) (4 5 N WATER 11) (3 4 V HOLDS 10) (2 3 V CAN 5) (2 3 AUX CAN 6) (1 3 VP (1 8) 9) (2 3 NP (7) 8) (2 3 N CAN 7) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 5 VP (2 14) 16) (2 5 S (8 13) 15) (2 5 VP (6 13) 14) (3 5 VP (10 12) 13) (4 5 NP (11) 12) (4 5 N WATER 11) (3 4 V HOLDS 10) (1 3 VP (1 8) 9) (2 3 NP (7) 8) (2 3 N CAN 7) (2 3 AUX CAN 6) (2 3 V CAN 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))
((:INPUT '(CAN CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 5 S (4 14) 17) (1 5 VP (2 14) 16) (2 5 S (8 13) 15) (2 5 VP (6 13) 14) (3 5 VP (10 12) 13) (4 5 NP (11) 12) (4 5 N WATER 11) (3 4 V HOLDS 10) (1 3 VP (1 8) 9) (2 3 NP (7) 8) (2 3 N CAN 7) (2 3 AUX CAN 6) (2 3 V CAN 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))

((:INPUT '(THE CAN CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 6 S (6 16) 20) (3 6 VP (8 15) 16) (3 6 S (10 15) 17) (4 6 VP (12 14) 15) (5 6 NP (13) 14) (5 6 N WATER 13) (4 5 V HOLDS 12) (3 4 V CAN 7) (3 4 AUX CAN 8) (2 4 VP (2 10) 11) (3 4 NP (9) 10) (3 4 N CAN 9) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ART THE 1))))
((:INPUT '(THE CAN CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((2 6 VP (3 16) 18) (2 6 S (5 16) 19) (1 6 S (6 16) 20) (3 6 VP (8 15) 16) (3 6 S (10 15) 17) (4 6 VP (12 14) 15) (5 6 NP (13) 14) (5 6 N WATER 13) (4 5 V HOLDS 12) (3 4 V CAN 7) (3 4 AUX CAN 8) (2 4 VP (2 10) 11) (3 4 NP (9) 10) (3 4 N CAN 9) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ART THE 1))))
((:INPUT '(THE CAN CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 6 S (6 16) 20) (2 6 S (5 16) 19) (2 6 VP (3 16) 18) (3 6 S (10 15) 17) (3 6 VP (8 15) 16) (4 6 VP (12 14) 15) (5 6 NP (13) 14) (5 6 N WATER 13) (4 5 V HOLDS 12) (2 4 VP (2 10) 11) (3 4 NP (9) 10) (3 4 N CAN 9) (3 4 AUX CAN 8) (3 4 V CAN 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ART THE 1))))
((:INPUT '(THE CAN CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 6 S (6 16) 20) (2 6 S (5 16) 19) (2 6 VP (3 16) 18) (3 6 S (10 15) 17) (3 6 VP (8 15) 16) (4 6 VP (12 14) 15) (5 6 NP (13) 14) (5 6 N WATER 13) (4 5 V HOLDS 12) (2 4 VP (2 10) 11) (3 4 NP (9) 10) (3 4 N CAN 9) (3 4 AUX CAN 8) (3 4 V CAN 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ART THE 1))))

((:INPUT '(THE LARGE CAN CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 7 S (7 18) 22) (2 7 S (8 18) 23) (4 7 VP (10 17) 18) (4 7 S (12 17) 19) (5 7 VP (14 16) 17) (6 7 NP (15) 16) (6 7 N WATER 15) (5 6 V HOLDS 14) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((3 7 VP (4 18) 20) (3 7 S (6 18) 21) (1 7 S (7 18) 22) (2 7 S (8 18) 23) (4 7 VP (10 17) 18) (4 7 S (12 17) 19) (5 7 VP (14 16) 17) (6 7 NP (15) 16) (6 7 N WATER 15) (5 6 V HOLDS 14) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 7 S (8 18) 23) (2 7 S (7 18) 22) (3 7 S (6 18) 21) (3 7 VP (4 18) 20) (4 7 S (12 17) 19) (4 7 VP (10 17) 18) (5 7 VP (14 16) 17) (6 7 NP (15) 16) (6 7 N WATER 15) (5 6 V HOLDS 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 7 S (8 18) 23) (2 7 S (7 18) 22) (3 7 S (6 18) 21) (3 7 VP (4 18) 20) (4 7 S (12 17) 19) (4 7 VP (10 17) 18) (5 7 VP (14 16) 17) (6 7 NP (15) 16) (6 7 N WATER 15) (5 6 V HOLDS 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

((:INPUT '(HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 3 VP (1 3) 4) (2 3 NP (2) 3) (2 3 N WATER 2) (1 2 V HOLDS 1))))
((:INPUT '(HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((1 3 VP (1 3) 4) (2 3 NP (2) 3) (2 3 N WATER 2) (1 2 V HOLDS 1))))
((:INPUT '(HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 3 VP (1 3) 4) (2 3 NP (2) 3) (2 3 N WATER 2) (1 2 V HOLDS 1))))
((:INPUT '(HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 3 VP (1 3) 4) (2 3 NP (2) 3) (2 3 N WATER 2) (1 2 V HOLDS 1))))

((:INPUT '(CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 4 S (4 8) 10) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((1 4 VP (2 8) 9) (1 4 S (4 8) 10) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 4 VP (2 8) 9) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))
((:INPUT '(CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 4 S (4 8) 10) (1 4 VP (2 8) 9) (2 4 VP (5 7) 8) (3 4 NP (6) 7) (3 4 N WATER 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))

((:INPUT '(LARGE CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 5 S (6 10) 13) (3 5 VP (7 9) 10) (4 5 NP (8) 9) (4 5 N WATER 8) (3 4 V HOLDS 7) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((2 5 VP (3 10) 11) (2 5 S (5 10) 12) (1 5 S (6 10) 13) (3 5 VP (7 9) 10) (4 5 NP (8) 9) (4 5 N WATER 8) (3 4 V HOLDS 7) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 5 S (6 10) 13) (2 5 S (5 10) 12) (2 5 VP (3 10) 11) (3 5 VP (7 9) 10) (4 5 NP (8) 9) (4 5 N WATER 8) (3 4 V HOLDS 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 5 S (6 10) 13) (2 5 S (5 10) 12) (2 5 VP (3 10) 11) (3 5 VP (7 9) 10) (4 5 NP (8) 9) (4 5 N WATER 8) (3 4 V HOLDS 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))

((:INPUT '(THE LARGE CAN HOLDS WATER) 'DFS 'T)
 (:EXPECTED ((1 6 S (7 12) 15) (2 6 S (8 12) 16) (4 6 VP (9 11) 12) (5 6 NP (10) 11) (5 6 N WATER 10) (4 5 V HOLDS 9) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS WATER) 'DFS 'NIL)
 (:EXPECTED ((3 6 VP (4 12) 13) (3 6 S (6 12) 14) (1 6 S (7 12) 15) (2 6 S (8 12) 16) (4 6 VP (9 11) 12) (5 6 NP (10) 11) (5 6 N WATER 10) (4 5 V HOLDS 9) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS WATER) 'BFS 'T)
 (:EXPECTED ((1 6 S (8 12) 16) (2 6 S (7 12) 15) (3 6 S (6 12) 14) (3 6 VP (4 12) 13) (4 6 VP (9 11) 12) (5 6 NP (10) 11) (5 6 N WATER 10) (4 5 V HOLDS 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS WATER) 'BFS 'NIL)
 (:EXPECTED ((1 6 S (8 12) 16) (2 6 S (7 12) 15) (3 6 S (6 12) 14) (3 6 VP (4 12) 13) (4 6 VP (9 11) 12) (5 6 NP (10) 11) (5 6 N WATER 10) (4 5 V HOLDS 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

((:INPUT '(CAN HOLDS CAN) 'DFS 'T)
 (:EXPECTED ((1 4 S (4 10) 12) (2 4 VP (5 9) 10) (3 4 NP (8) 9) (3 4 N CAN 8) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS CAN) 'DFS 'NIL)
 (:EXPECTED ((3 4 V CAN 6) (3 4 AUX CAN 7) (1 4 VP (2 10) 11) (1 4 S (4 10) 12) (2 4 VP (5 9) 10) (3 4 NP (8) 9) (3 4 N CAN 8) (2 3 V HOLDS 5) (1 2 V CAN 1) (1 2 AUX CAN 2) (1 2 NP (3) 4) (1 2 N CAN 3))))
((:INPUT '(CAN HOLDS CAN) 'BFS 'T)
 (:EXPECTED ((1 4 VP (2 10) 11) (2 4 VP (5 9) 10) (3 4 NP (8) 9) (3 4 N CAN 8) (3 4 AUX CAN 7) (3 4 V CAN 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))
((:INPUT '(CAN HOLDS CAN) 'BFS 'NIL)
 (:EXPECTED ((1 4 S (4 10) 12) (1 4 VP (2 10) 11) (2 4 VP (5 9) 10) (3 4 NP (8) 9) (3 4 N CAN 8) (3 4 AUX CAN 7) (3 4 V CAN 6) (2 3 V HOLDS 5) (1 2 NP (3) 4) (1 2 N CAN 3) (1 2 AUX CAN 2) (1 2 V CAN 1))))

((:INPUT '(LARGE CAN HOLDS LARGE CAN) 'DFS 'T)
 (:EXPECTED ((1 6 S (6 14) 17) (3 6 VP (7 13) 14) (4 6 NP (8 11) 13) (5 6 N CAN 11) (4 5 ADJ LARGE 8) (3 4 V HOLDS 7) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS LARGE CAN) 'DFS 'NIL)
 (:EXPECTED ((5 6 V CAN 9) (5 6 AUX CAN 10) (5 6 NP (11) 12) (2 6 VP (3 14) 15) (2 6 S (5 14) 16) (1 6 S (6 14) 17) (3 6 VP (7 13) 14) (4 6 NP (8 11) 13) (5 6 N CAN 11) (4 5 ADJ LARGE 8) (3 4 V HOLDS 7) (2 3 V CAN 2) (2 3 AUX CAN 3) (2 3 NP (4) 5) (1 3 NP (1 4) 6) (2 3 N CAN 4) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS LARGE CAN) 'BFS 'T)
 (:EXPECTED ((1 6 S (6 14) 17) (2 6 S (5 14) 16) (2 6 VP (3 14) 15) (3 6 VP (7 13) 14) (4 6 NP (8 11) 13) (5 6 NP (11) 12) (5 6 N CAN 11) (5 6 AUX CAN 10) (5 6 V CAN 9) (4 5 ADJ LARGE 8) (3 4 V HOLDS 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))
((:INPUT '(LARGE CAN HOLDS LARGE CAN) 'BFS 'NIL)
 (:EXPECTED ((1 6 S (6 14) 17) (2 6 S (5 14) 16) (2 6 VP (3 14) 15) (3 6 VP (7 13) 14) (4 6 NP (8 11) 13) (5 6 NP (11) 12) (5 6 N CAN 11) (5 6 AUX CAN 10) (5 6 V CAN 9) (4 5 ADJ LARGE 8) (3 4 V HOLDS 7) (1 3 NP (1 4) 6) (2 3 NP (4) 5) (2 3 N CAN 4) (2 3 AUX CAN 3) (2 3 V CAN 2) (1 2 ADJ LARGE 1))))

((:INPUT '(THE LARGE CAN HOLDS LARGE CAN) 'DFS 'T)
 (:EXPECTED ((1 7 S (7 16) 19) (2 7 S (8 16) 20) (4 7 VP (9 15) 16) (5 7 NP (10 13) 15) (6 7 N CAN 13) (5 6 ADJ LARGE 10) (4 5 V HOLDS 9) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS LARGE CAN) 'DFS 'NIL)
 (:EXPECTED ((6 7 V CAN 11) (6 7 AUX CAN 12) (6 7 NP (13) 14) (3 7 VP (4 16) 17) (3 7 S (6 16) 18) (1 7 S (7 16) 19) (2 7 S (8 16) 20) (4 7 VP (9 15) 16) (5 7 NP (10 13) 15) (6 7 N CAN 13) (5 6 ADJ LARGE 10) (4 5 V HOLDS 9) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS LARGE CAN) 'BFS 'T)
 (:EXPECTED ((1 7 S (8 16) 20) (2 7 S (7 16) 19) (3 7 S (6 16) 18) (3 7 VP (4 16) 17) (4 7 VP (9 15) 16) (5 7 NP (10 13) 15) (6 7 NP (13) 14) (6 7 N CAN 13) (6 7 AUX CAN 12) (6 7 V CAN 11) (5 6 ADJ LARGE 10) (4 5 V HOLDS 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN HOLDS LARGE CAN) 'BFS 'NIL)
 (:EXPECTED ((1 7 S (8 16) 20) (2 7 S (7 16) 19) (3 7 S (6 16) 18) (3 7 VP (4 16) 17) (4 7 VP (9 15) 16) (5 7 NP (10 13) 15) (6 7 NP (13) 14) (6 7 N CAN 13) (6 7 AUX CAN 12) (6 7 V CAN 11) (5 6 ADJ LARGE 10) (4 5 V HOLDS 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

((:INPUT '(THE LARGE CAN CAN CAN THE LARGE WATER) 'DFS 'T)
 (:EXPECTED ((1 9 S (7 30) 34) (2 9 S (8 30) 35) (4 9 VP (10 29) 30) (4 9 S (12 29) 31) (5 9 VP (14 27) 29) (6 9 NP (23 24 25) 27) (7 9 NP (24 25) 28) (8 9 N WATER 25) (7 8 ADJ LARGE 24) (6 7 ART THE 23) (5 6 V CAN 14) (5 6 AUX CAN 15) (3 6 VP (4 18) 19) (3 6 S (6 18) 20) (1 6 S (7 18) 21) (2 6 S (8 18) 22) (4 6 VP (9 17) 18) (5 6 NP (16) 17) (5 6 N CAN 16) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN CAN THE LARGE WATER) 'DFS 'NIL)
 (:EXPECTED ((8 9 NP (25) 26) (3 9 VP (4 30) 32) (3 9 S (6 30) 33) (1 9 S (7 30) 34) (2 9 S (8 30) 35) (4 9 VP (10 29) 30) (4 9 S (12 29) 31) (5 9 VP (14 27) 29) (6 9 NP (23 24 25) 27) (7 9 NP (24 25) 28) (8 9 N WATER 25) (7 8 ADJ LARGE 24) (6 7 ART THE 23) (5 6 V CAN 14) (5 6 AUX CAN 15) (3 6 VP (4 18) 19) (3 6 S (6 18) 20) (1 6 S (7 18) 21) (2 6 S (8 18) 22) (4 6 VP (9 17) 18) (5 6 NP (16) 17) (5 6 N CAN 16) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN CAN THE LARGE WATER) 'BFS 'T)
 (:EXPECTED ((1 9 S (8 30) 35) (2 9 S (7 30) 34) (3 9 S (6 30) 33) (3 9 VP (4 30) 32) (4 9 S (12 29) 31) (4 9 VP (10 29) 30) (5 9 VP (14 28) 29) (6 9 NP (23 24 25) 28) (7 9 NP (24 25) 27) (8 9 NP (25) 26) (8 9 N WATER 25) (7 8 ADJ LARGE 24) (6 7 ART THE 23) (1 6 S (8 18) 22) (2 6 S (7 18) 21) (3 6 S (6 18) 20) (3 6 VP (4 18) 19) (4 6 VP (9 17) 18) (5 6 NP (16) 17) (5 6 N CAN 16) (5 6 AUX CAN 15) (5 6 V CAN 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN CAN THE LARGE WATER) 'BFS 'NIL)
 (:EXPECTED ((1 9 S (8 30) 35) (2 9 S (7 30) 34) (3 9 S (6 30) 33) (3 9 VP (4 30) 32) (4 9 S (12 29) 31) (4 9 VP (10 29) 30) (5 9 VP (14 28) 29) (6 9 NP (23 24 25) 28) (7 9 NP (24 25) 27) (8 9 NP (25) 26) (8 9 N WATER 25) (7 8 ADJ LARGE 24) (6 7 ART THE 23) (1 6 S (8 18) 22) (2 6 S (7 18) 21) (3 6 S (6 18) 20) (3 6 VP (4 18) 19) (4 6 VP (9 17) 18) (5 6 NP (16) 17) (5 6 N CAN 16) (5 6 AUX CAN 15) (5 6 V CAN 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

((:INPUT '(THE LARGE CAN CAN WATER THE LARGE CAN) 'DFS 'T)
 (:EXPECTED ((8 9 V CAN 23) (8 9 AUX CAN 24) (8 9 NP (25) 26) (6 9 NP (21 22 25) 27) (7 9 NP (22 25) 28) (8 9 N CAN 25) (7 8 ADJ LARGE 22) (6 7 ART THE 21) (3 6 VP (4 16) 17) (3 6 S (6 16) 18) (1 6 S (7 16) 19) (2 6 S (8 16) 20) (4 6 VP (9 15) 16) (5 6 NP (14) 15) (5 6 N WATER 14) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN WATER THE LARGE CAN) 'DFS 'NIL)
 (:EXPECTED ((8 9 V CAN 23) (8 9 AUX CAN 24) (8 9 NP (25) 26) (6 9 NP (21 22 25) 27) (7 9 NP (22 25) 28) (8 9 N CAN 25) (7 8 ADJ LARGE 22) (6 7 ART THE 21) (3 6 VP (4 16) 17) (3 6 S (6 16) 18) (1 6 S (7 16) 19) (2 6 S (8 16) 20) (4 6 VP (9 15) 16) (5 6 NP (14) 15) (5 6 N WATER 14) (4 5 V CAN 9) (4 5 AUX CAN 10) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (3 4 V CAN 3) (3 4 AUX CAN 4) (3 4 NP (5) 6) (1 4 NP (1 2 5) 7) (2 4 NP (2 5) 8) (3 4 N CAN 5) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN WATER THE LARGE CAN) 'BFS 'T)
 (:EXPECTED ((6 9 NP (21 22 25) 28) (7 9 NP (22 25) 27) (8 9 NP (25) 26) (8 9 N CAN 25) (8 9 AUX CAN 24) (8 9 V CAN 23) (7 8 ADJ LARGE 22) (6 7 ART THE 21) (1 6 S (8 16) 20) (2 6 S (7 16) 19) (3 6 S (6 16) 18) (3 6 VP (4 16) 17) (4 6 VP (9 15) 16) (5 6 NP (14) 15) (5 6 N WATER 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))
((:INPUT '(THE LARGE CAN CAN WATER THE LARGE CAN) 'BFS 'NIL)
 (:EXPECTED ((6 9 NP (21 22 25) 28) (7 9 NP (22 25) 27) (8 9 NP (25) 26) (8 9 N CAN 25) (8 9 AUX CAN 24) (8 9 V CAN 23) (7 8 ADJ LARGE 22) (6 7 ART THE 21) (1 6 S (8 16) 20) (2 6 S (7 16) 19) (3 6 S (6 16) 18) (3 6 VP (4 16) 17) (4 6 VP (9 15) 16) (5 6 NP (14) 15) (5 6 N WATER 14) (3 5 VP (3 12) 13) (4 5 NP (11) 12) (4 5 N CAN 11) (4 5 AUX CAN 10) (4 5 V CAN 9) (1 4 NP (1 2 5) 8) (2 4 NP (2 5) 7) (3 4 NP (5) 6) (3 4 N CAN 5) (3 4 AUX CAN 4) (3 4 V CAN 3) (2 3 ADJ LARGE 2) (1 2 ART THE 1))))

))

